#include <cstring>
#include "binarySearchTree.h"
#include "util.h"



static node *root = nullptr;
/**/
static int _keyCmp(const char *k1, const char *k2)
{
    UTIL_ASSERT(k1 != nullptr);
    UTIL_ASSERT(k2 != nullptr);

    return util_strcmp(k1, k2);
}
/**/
static int _size(const struct node *n)
{
    if(n == nullptr)
        return 0;
    else
        return n->size;

}
/**/
struct node *binarySearchTreeCreate(char *key, int val, int size)
{
    struct node *n = nullptr;

    n = (struct node *)util_malloc(sizeof(struct node));
#if 0
    if(n == nullptr)
    {
        printf_s("malloc size:%d memory failed!\r\n", sizeof(struct node));
        return nullptr;
    }
#else
    UTIL_ASSERT(n != nullptr);
#endif

    util_memset((void *)n, 0, sizeof(struct node));

    UTIL_ASSERT(key != nullptr);

    n->key = key;
    n->val = val;
    n->size = size;
    n->left = n->right = nullptr;

    return n;
}
/**/
static struct node * _bstPut(struct node *n, char *key, int val)
{
    if(n == nullptr)
       return binarySearchTreeCreate(key, val, 1);

    int cmp = _keyCmp(key, n->key);


    if(cmp < 0)
        n->left = _bstPut(n->left, key, val);
    else if (cmp > 0)
        n->right = _bstPut(n->right, key, val);
    else
        n->val = val;

    n->size = 1 + _size(n->left) + _size(n->right) ;

    return n;


}
/**/
int binarySearchTreePut(char *key, int val)
{
    int ret = 0;

    root = _bstPut(root, key, val);

    return ret;
}
/**/
static void _bstDestroy(struct node *n)
{
    if(n == nullptr)
        return;
    if(n->left == nullptr && n->right == nullptr)
    {
        util_free(n);
        return;
    }
    if(n->left)
    {
        _bstDestroy(n->left);
        n->left = nullptr;
    }

    if(n->right)
    {
        _bstDestroy(n->right);
        n->right = nullptr;
    }
   
}
/**/
void binarySearchTreeDestroy(void)
{
    _bstDestroy(root);
}
